LOJ6276 果树

思维难度较大，代码难度巨大，细节超多

题意：

给定一棵树，每个点有个颜色，询问特殊路径的数量

其中，定义特殊路径$(u,v)$为从u到v每个点颜色都不同的路径

$(u,v)=(v,u)$

特别的，每种颜色至多出现20次

题解：

每种颜色至多20次显然是问题的突破口

这样我们可以先假设所有点两两都是满足的，然后在同种颜色集合内两两枚举节点，对与两者相关联的点统一做关系消除，因为只要同时经过这两点的路径都一定是不合法的

这种“关联”显然是连贯的，而树上连贯的关系又想到什么？dfs序！

在本题中，由于关联是双向的，我们将dfs序拓展成矩阵，消除关系就相当于在矩阵上放矩形（打阴影）

最后答案就是没被覆盖的部分

求矩阵面积并你又想到了啥？扫描线+线段树！

套用模板即可

然鹅细节最多的部分在下面：

我们对枚举的同色两点进行如下分类讨论：

假设$deep_x<=deep_y$且$col_x=col_y$

已知如下一棵树：

ver0

dfs矩阵是这样的的：

tab0

SIT1： 无祖先关系

ver1

在上图中，x=2，y=3

发现此时会因为这两点导致关系不成立的是x的子树和y的子树（见图上的两个蓝框

这两部分由于都是子树，因此在dfs序上都是连续的（见下图的蓝色部分和绿色部分

可以在矩阵上打上两块完整的矩形（见下图的灰色部分

tab1

代码中只要计算dfs序上连续部分的头和尾就就可以得到矩形的四个顶点

SIT2： 有祖先关系

ver2

在上图中，x=1，y=6，且x是y的祖先

发现此时会因为这两点导致关系不成立的是y的子树和整棵树刨去点2的子树后的部分（见图上的两个蓝框

而这个点2是什么呢？它是x的所有儿子中距离y最近的一个，可以表示为点z

因此蓝框部分又可以叫做y的子树和整棵树刨去z的子树后的部分

z的位置怎么计算呢？

发现z是y的祖先，且已知z到y的距离，因此可以用倍增lca的方法预处理出每个点2幂次倍的祖先，此时再对z-y距离二进制分解，对等于1的二进制位做爬升处理

y的子树部分与SIT1相同

那整棵树刨去z的子树后的部分在dfs序上怎么得到呢？

由于是刨去，因此该部分可能是两段不连续的区间

在下图中，红线部分是z的子树，绿色是y的子树，两种蓝色是刨去后剩下的两段

tab2

代码中可以先将绿色与深蓝色部分打阴影

处理好后再将绿色与浅蓝色部分打阴影

添加阴影上下边和求面积并时注意点与长度的关系，即处理好是否需要+1变成左闭右开区间

最后面积算好后记得除以2,因为$(u,v)=(v,u)$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int f[N][20],en,h[N],sz[N],id[N],n,cnt,len[N<<2],tag[N<<2],ln,d[N];
vector<int> col[N];
long long ans;

struct edge{
    int n,v;
}e[N<<1];
/*阴影的上下边界线*/
struct line{
    int l,r,h,op; //op=1是上线，op=-1是下线
    inline bool operator < (const line &nt) const {
        return h<nt.h;
    }
}a[N<<6];
/*线段树部分*/
void pushup(int x,int l,int r){
    if(tag[x]){
        len[x]=r-l+1;
    }
    else{
        if(l^r) len[x]=len[x<<1]+len[x<<1|1];
        else len[x]=0;
    }
}

void up(int x,int l,int r,int p,int q,int v){
    if(p<=l&&r<=q){
        tag[x]+=v;
        pushup(x,l,r);
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid) up(x<<1,l,mid,p,q,v);
    if(q>mid) up(x<<1|1,mid+1,r,p,q,v);
    pushup(x,l,r);
}

void add(int x,int y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}
/*预处理部分*/
void dfs(int x){
    sz[x]=1;
    d[x]=d[f[x][0]]+1;
    id[x]=++cnt;
    for(int i=1;i<=16;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==f[x][0]) continue;
        f[y][0]=x;
        dfs(y);
        sz[x]+=sz[y];
    }
}
/*倍增lca*/
int lca(int x,int y){
    for(int i=16;~i;i--) if(d[f[y][i]]>=d[x])
        y=f[y][i];
    if(x==y) return x;
    for(int i=16;~i;i--) if(f[x][i]^f[y][i]){
        x=f[x][i];
        y=f[y][i];
    }
    return f[x][0];
}
/*二进制跳跃找祖先*/
int getf(int x,int k){
    for(int i=16;~i;i--) if(k>>i&1)
        x=f[x][i];
    return x;
}
/*添加阴影的上下边界线*/
void addline(int x,int y,int xx,int yy){ //(x,y)是矩形的左上角，(xx,yy)是矩形的右下角
    a[++ln]=(line){x,xx,y,1}; //上线
    a[++ln]=(line){x,xx,yy+1,-1}; //下线
    a[++ln]=(line){y,yy,x,1}; //对称过来的上线
    a[++ln]=(line){y,yy,xx+1,-1}; //对称过来的下线
}

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++) col[read(x)].push_back(i);
    for(int i=1,x,y;i<n;i++){
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    /*预处理出dfs序和fa[][]等信息*/
    dfs(1);
    /*打阴影*/
    for(int i=1;i<=n;i++) //枚举颜色
        for(int j=0;j<col[i].size();j++)
            for(int k=j+1;k<col[i].size();k++){ //两两枚举点
                int x=col[i][j],y=col[i][k];
                if(d[x]>d[y]) swap(x,y);
                int LCA=lca(x,y);
                if(LCA==x){ //x是y祖先的情况
                    int z=getf(y,d[y]-d[x]-1); //求z的位置
                    int xx=id[z]-1;
                    int yy=id[y]+sz[y]-1;
                    x=1;
                    y=id[y];
                    /*(x,y)是矩形的左上角，(xx,yy)是矩形的右下角，下同*/
                    if(x<=xx) addline(x,y,xx,yy); //前半段
                    x=id[z]+sz[z],xx=n;
                    if(x<=xx) addline(x,y,xx,yy); //后半段
                }
                else{
                    int xx=id[x]+sz[x]-1,yy=id[y]+sz[y]-1;
                    x=id[x];y=id[y];
                    addline(x,y,xx,yy); //完整的一段
                }
            }
    /*求面积并部分，模板*/
    sort(a+1,a+1+ln);
    for(int i=1;i<ln;i++){
        up(1,1,n,a[i].l,a[i].r,a[i].op);
        ans+=1ll*len[1]*(a[i+1].h-a[i].h);
    }
    write(1ll*(1+n)*n-ans>>1ll); //一块等腰直角三角形面积减去一半的阴影面积
}

如果你写挂了，就请多检查检查你的打阴影部分

赏

fighter